package imooc_math.sort;

import java.util.Arrays;

import resource.SortTestHelper;

public class QuickSort2Way {
	private static int partition(Comparable[] arry,int l,int r){
		int exchangeIndex=(int)(Math.random()*(r-l+1))+l;//快排的优化：将数组索引为l位置的值与[l,r]任意位置的值进行交换，保证arry[l]在整个数组中最小的概率极其小
		swap(arry,l,exchangeIndex);//为什么要做这个优化：因为在对近乎有序的数组进行排序时，很可能出现[l,r]范围内l最小。如果每次索引为l的值都是最小的话，快速排序就会退化成O（n^2）的算法
		Object v=arry[l];//进行比较的数
		int i=l+1;
		int j=r;
		//[l,i)<v,(j,r]>v
		while(true){
			while(i<=r&&arry[i].compareTo(v)<0){//得到i的最终位置
				i++;
			}
			while(j>=l+1&&arry[j].compareTo(v)>0){
				j--;
			}
			if(i>j){
				break;
			}
			swap(arry,i,j);
			i++;
			j--;
		}
		swap(arry,l,j);
		return j;
	}
	private static void sort(Comparable[] arry,int l,int r){
		if(l>=r){
			return;
		}
		int j=partition(arry,l,r);
		sort(arry,l,j);
		sort(arry,j+1,r);
	
	}
	public static Object[] sort(Comparable[] arry){
		int n=arry.length;
		sort(arry,0,n-1);	
		return arry;
	}
	public static void swap(Object [] arr,int a,int b){
		Object t=arr[a];
		arr[a]=arr[b];
		arr[b]=t;
	}
	public static void main(String[] args) {
		/*Integer[] arry=new  SortTestHelper().generateNearlyOrderedArray(20, 10);
		System.out.println(Arrays.toString(arry));
		sort(arry);
		System.out.println(Arrays.toString(arry));*/
		int n=30000;
		int swapTimes=10;
		//Integer[] arry=new  SortTestHelper().generateNearlyOrderedArray(n, swapTimes);
		Integer[] arry=new  SortTestHelper().generateRandomArray(n,0,10);
		SortTestHelper sth=new SortTestHelper();
		Integer[] arryCopy=Arrays.copyOf(arry,arry.length);
		
		sth.testSort("imooc_math.MergeSort", arry);
		sth.testSort("imooc_math.QuickSort", arryCopy);
		sth.testSort("imooc_math.QuickSort2Way", arryCopy);
	}
}
